package sort;

import java.util.Arrays;


public class Sort {
    public static void main(String[] args) {
//        int[] arr={1,4,2,3,1};
//        arr=insertSort(arr);
//        System.out.println(Arrays.toString(arr));
        int[] arr={1,4,2,3};
        System.out.println("=======");
        arr=count(arr);
        System.out.println(Arrays.toString(arr));
    }
    //插入排序
    public static int[] insertSort(int[] arr) {
        //依次选出最后一个元素进行比较
        for (int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            //和前面的所有元素进行比较
            for (;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }else break;
            }
            //把tem填补到孔雀位置
            arr[j+1]=temp;
        }
        return arr;
    }
    //希尔排序
    public static int[] shellSort(int[] arr){
        int gap=arr.length;
        while (gap>1){
            gap=gap/2;
            shell(arr,gap);
        }
        return arr;
    }
    public static void shell(int[] arr, int gap) {
        for (int i=gap;i<arr.length;i++){
            int temp=arr[i];
            int j=i-gap;
            for (;j>=0;j-=gap){
                if (arr[j]>temp){
                    arr[j+gap]=arr[j];
                }else break;
            }
            arr[j+gap]=temp;
        }
    }
    //选择排序
    public static int[] select(int[] arr){
        for (int i=0;i<arr.length;i++){
            int min=i;
            for (int j=i+1;j<arr.length;j++){
                if (arr[j]<arr[min]){
                    min=j;
                }
            }
            swap(min,i,arr);
        }
        return arr;
    }
    //双向选择排序
    public static int[] select2(int[] arr){
        int i=0;
        int j=arr.length-1;
        while (i<j){
            int min=i;
            int max=i;
            for (int a=i+1;a<=j;a++){
                if (arr[a]<arr[min]){
                    min=a;
                }
                if (arr[a]>arr[max]){
                    max=a;
                }
            }
            swap(min,i,arr);
            if(max==i){
                max=min;
            }
            swap(max,j,arr);
            i++;
            j--;
        }
        return arr;
    }
    //快速排序
    public static int[] quickSort(int[] arr){
        //quick(0,arr.length-1,arr);
        dole(0,arr.length-1,arr);
        return arr;
    }

    private static void quick(int start, int end, int[] arr) {
        if(start>=end){
            return;
        }
        int pivot=hore(start,end,arr);
        quick(start,pivot-1,arr);
        quick(pivot+1,end,arr);
    }

    private static int hore(int left, int right, int[] arr) {
        int temp=arr[left];
        int l=left;
        while (left<right){
            while (left<right&&arr[right]>=temp){
                right--;
            }
            while (left<right&&arr[left]<=temp){
                left++;
            }
            swap(left,right,arr);
        }
        swap(l,left,arr);
        return l;
    }
    public static void dole(int start, int end, int[] arr){
        if(start>=end){
            return;
        }
        int pivot=dolefun(start,end,arr);
        dole(start,pivot-1,arr);
        dole(pivot+1,end,arr);
    }

    private static int dolefun(int start, int end, int[] arr) {
        int tmp=arr[start];
        while (start<end){
            while (start<end&&arr[end]>=tmp){
                end--;
            }
            arr[start]=arr[end];
            while (start<end&&arr[start]<=tmp){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=tmp;
        return start;
    }
    //归并排序
    public static int[] mergeOrder(int[] arr){
        mergefun(0,arr.length-1,arr);
        return arr;
    }
    private static void mergefun(int l, int r, int[] arr) {
        if (l>=r){
            return;
        }
        int mid=(l+r)/2;
        mergefun(l,mid,arr);
        mergefun(mid+1,r,arr);
        merge(l,r,mid,arr);
    }
    private static void merge(int l, int r, int mid, int[] arr) {
        int s1=l;int e1=mid;int s2=mid+1;int e2=r;int[] tmp=new int[r-l+1];int i=0;
        while (s1<=e1&&s2<=e2){
            if(arr[s1]<arr[s2]){
                tmp[i]=arr[s1];
                i++;
                s1++;
            }else {
                tmp[i]=arr[s2];
                i++;
                s2++;
            }
        }
        while (s1<=e1){
            tmp[i]=arr[s1];
            i++;
            s1++;
        }
        while (s2<=e2){
            tmp[i]=arr[s2];
            i++;
            s2++;
        }
        for (int j=0;j<tmp.length;j++){
            arr[j+l]=tmp[j];
        }
    }
    //冒泡排序
    public static int[] buble(int[] arr){
        Boolean flag=true;
        for (int i=0;i<arr.length;i++){
            for (int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    swap(j,j+1,arr);
                    flag=flag;
                }
            }
            if (flag){
                return arr;
            }
        }
        return arr;
    }
    //计数排序
    public static int[] count(int[] arr){
        int max=arr[0];
        int min=arr[0];
        for (int i=1;i<arr.length;i++){
            if (arr[i]<min){
                min=arr[i];
            }
            if (arr[i]>max){
                max=arr[i];
            }
        }
        int[] tmp=new int[max-min+1];
        for (int i=0;i<arr.length;i++){
            tmp[arr[i]-min]++;
        }
        int index=0;
        for (int i=0;i<tmp.length;i++){
            while (tmp[i]>0){
                arr[index]=i+min;
                index++;
                tmp[i]--;
            }
        }
        return arr;
    }
    private static void swap(int i, int j,int[] arr) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
       
    }
}
